class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        
        unordered_map<int,int> has;
        vector<int> vecArr;
        for(int i=0;i<nums.size();++i){
            ++has[nums[i]];
            if(has[nums[i]]==1){
                vecArr.push_back(nums[i]);
            }
        }
        vecArr.push_back(-1);
        sort(vecArr.begin(),vecArr.end());
        vector<int> dp(vecArr.size());
        for(int i=1;i<vecArr.size();++i){
            int x=vecArr[i];
            int c=has[x];
            int j=i-1;
            while(vecArr[j]>=x-1){
                --j;
            }
            dp[i]=max(dp[i-1],dp[j]+x*c);
        }

        return dp.back();
    }
};
